home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / D_Node.C < prev    next >
C/C++ Source or Header  |  1992-05-15  |  7KB  |  179 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/D_Node.h>
  14.  
  15. // CoolD_Node -- Simple constructor that allocates enough storage for a vector of
  16. //           pointers to CoolD_Node objects
  17. // Input:    None
  18. // Output:   None
  19.  
  20. template <class Type, int nchild> 
  21. CoolD_Node<Type,nchild>::CoolD_Node<Type,nchild> () {
  22.   sub_trees.set_alloc_size(nchild);        // fix growth ratio instead
  23.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  24.     this->sub_trees.push(NULL);            // Insure NULL pointer value
  25.   if (this->compare_s == NULL)            // If no compare function
  26.     this->compare_s = &Type##_default_CoolD_Node_compare; // Default
  27. }
  28.  
  29.  
  30. // CoolD_Node -- Simple constructor that allocates enough storage for a vector of
  31. //           pointers to CoolD_Node objects and assigns an initial data value
  32. // Input:    Data slot value
  33. // Output:   None
  34.  
  35. template <class Type, int nchild> 
  36. CoolD_Node<Type,nchild>::CoolD_Node<Type,nchild> (const Type& value) {
  37.   for (int i = 0; i < nchild; i++)        // For each pointer in vector
  38.     this->sub_trees.push(NULL);            // Insure NULL pointer value
  39.   if (this->compare_s == NULL)            // If no compare function
  40.     this->compare_s = &Type##_default_CoolD_Node_compare; // Default
  41.   this->set(value);                // Copy initial data value
  42. }
  43.  
  44.  
  45. // CoolD_Node -- Copy constructor makes deep copy
  46. // Input:    Reference to CoolD_Node
  47. // Output:   None
  48.  
  49. template <class Type, int nchild> 
  50. CoolD_Node<Type,nchild>::CoolD_Node<Type,nchild> (const CoolD_Node<Type,nchild>& n) {
  51.   for (int i = 0; i < n.sub_trees.length(); i++) // For each pointer in vector
  52.     this->sub_trees.push(copy_nodes(n.sub_trees[i])); // Deep copy of subnodes
  53.   this->set(n.get());                // Copy data value
  54.   this->compare_s = n.compare_s;        // Set compare method
  55. }
  56.  
  57.  
  58. // ~CoolD_Node -- Destructor for the CoolD_Node<Type,nchild> class
  59. // Input:     None
  60. // Output:    None
  61.  
  62. template <class Type, int nchild> 
  63. CoolD_Node<Type,nchild>::~CoolD_Node<Type,nchild> () {
  64.   for (int i = 0; i < this->num_subtrees(); i++) // For each pointer in vector
  65.     delete this->sub_trees[i];            // Invoke destructor
  66. }
  67.  
  68.  
  69. // is_leaf -- Determine if node has any children
  70. // Input:     None
  71. // Output:    TRUE if no children, else FALSE
  72.  
  73. template <class Type, int nchild> 
  74. Boolean CoolD_Node<Type,nchild>::is_leaf () const {
  75.   for (int i = 0; i < this->num_subtrees(); i++)
  76.     if (this->sub_trees[i])
  77.       return (FALSE);
  78.   return TRUE;
  79. }
  80.  
  81.  
  82. // operator= -- Overload the assignment operator to copy all values from one
  83. //              node object to another. This routine could potentially result
  84. //              in a complete deep copy, since for each valid sub_tree pointer,
  85. //              a new node is allocated and its sub_tree pointers copied.
  86. // Input:       Reference to CoolD_Node
  87. // Output:      Rererence to updated CoolD_Node
  88.  
  89. template <class Type, int nchild> 
  90. CoolD_Node<Type,nchild>& CoolD_Node<Type,nchild>::operator= (const CoolD_Node<Type,nchild>& n) {
  91.   int i;
  92.   for (i = 0; i < this->num_subtrees(); i++) // Recursively delete old tree
  93.     delete this->sub_trees.pop();         // and pop from vector
  94.   for (i = 0; i < n.num_subtrees(); i++)     // Push in new subtrees
  95.     this->sub_trees.push(copy_nodes(n.sub_trees[i]));
  96.   this->set(n.get());                // Copy data value
  97.   return *this;                    // Return reference
  98. }
  99.  
  100. // insert_before -- Insert sub-tree pointer to child before the specified
  101. //                  zero-relative sub-tree index (numbered from left to right)
  102. // Input:           Pointer to child node, zero-relative index
  103. // Output:          TRUE/FALSE
  104.  
  105. template <class Type, int nchild> 
  106. Boolean CoolD_Node<Type,nchild>::insert_before (const CoolD_Node<Type,nchild>& n, int index) {
  107. #if ERROR_CHECKING
  108.   if (index < 0) {                // If index out of range
  109.     this->index_error ("insert_before", index);    // Raise exception
  110.     return FALSE;                // Return failure status
  111.   }
  112. #endif
  113.   this->sub_trees.insert_before(&n, index);    // Pointer to new sub-tree
  114.   return TRUE;                    // Return success status
  115. }
  116.  
  117.  
  118. // insert_after -- Insert sub-tree pointer to child after the specified
  119. //                 zero-relative sub-tree index (numbered from left to right)
  120. // Input:          Pointer to child node, zero-relative index
  121. // Output:         TRUE/FALSE
  122.  
  123. template <class Type, int nchild> 
  124. Boolean CoolD_Node<Type,nchild>::insert_after (const CoolD_Node<Type,nchild>& n, int index) {
  125. #if ERROR_CHECKING
  126.   if (index < 0) {                // If index out of range
  127.     this->index_error ("insert_after", index);    // Raise exception
  128.     return FALSE;                // Return failure status
  129.   }
  130. #endif
  131.   this->sub_trees.insert_after(&n, index);    // Pointer to new sub-tree
  132.   return TRUE;                    // Return success status
  133. }
  134.  
  135.  
  136. // copy_nodes -- Copies this node and all its subnodes
  137. // Input:       pointer to node to be copied
  138. // Output:      pointer to new copy of node with all new subnodes.
  139.  
  140. template <class Type, int nchild>
  141. CoolD_Node<Type,nchild>* CoolD_Node<Type,nchild>::copy_nodes (const CoolD_Node<Type,nchild>* n) const {
  142.   if (n == NULL)                
  143.     return NULL;
  144.   CoolD_Node<Type,nchild>* new_n = new CoolD_Node<Type,nchild>; 
  145.   for (int i = 0; i < n->num_subtrees(); i++)    // For each pointer in vector
  146.     new_n->sub_trees.push(copy_nodes(n->sub_trees[i])); // Deep copy of subnodes
  147.   new_n->data = n->data;                   // Copy data value
  148.   return new_n;                      // Return copied node.
  149. }
  150.  
  151.  
  152. // index_error -- Raise exception for invalid index
  153. // Input:         Function name, invalid index
  154. // Output:        None
  155.  
  156. template <class Type, int nchild> 
  157. void CoolD_Node<Type,nchild>::index_error (const char* fcn, int n) {
  158.   //RAISE Error, SYM(CoolD_Node), SYM(Out_Of_Range),
  159.   printf ("CoolD_Node<%s,%d>::%s: Index %d out of range.\n", #Type, nchild,
  160.       fcn, n);
  161.   abort ();
  162. }
  163.  
  164.  
  165. // default_CoolD_Node_compare -- Default node comparison function utilizing builtin
  166. //                           less than, equal, and greater than operators
  167. // Input:                    Reference to two Type data values
  168. // Output:                   -1, 0, or 1 if less than, equal to, or greater than
  169.  
  170. template <class Type, int nchild> CoolD_Node {
  171.   int Type##_default_CoolD_Node_compare (const Type& v1, const Type& v2) {
  172.     if (v1 == v2)                // If data items equal
  173.       return 0;                    // Return zero
  174.     if (v1 < v2)                // If this less than data
  175.       return -1;                // Return negative one
  176.     return 1;                    // Else return positive one
  177.   }
  178. }
  179.